package java学习.算法.二叉树;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/3/17 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class TwoTree {
   static class Node<V>{
        Node left;
        Node right;
        V value;

       public Node(V i) {
            value = i;
       }

       @Override
       public String toString() {
           return
//                   "Node{" +
//                   "left=" + left +
//                   ", right=" + right +
                  value + "";
       }
   }

    public static void first(Node head){
        if (head==null){
            return;
        }
        System.out.print(head.value+"   ");

        first(head.left);

        first(head.right);
    }
    // 非递归先序1
    public static void pre(Node head){

        if (head!=null){
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()){
                Node cur = stack.pop();
                System.out.print(cur.value+"   ");

                if (cur.right!=null){
                    stack.push(cur.right);
                }
                if (cur.left!=null){
                    stack.push(cur.left);
                }
            }
        }

    }
    // 非递归先序2
    public static void pre1(Node head) {
        System.out.print("pre-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while (!stack.isEmpty()) {
                // 弹出就打印
                head = stack.pop();
                System.out.print(head.value + " ");
                // 右孩子不为空，压右
                if (head.right != null) {
                    stack.push(head.right);
                }
                // 左孩子不为空，压左
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }
    public static void behind(Node head){

        if (head!=null){
            Stack<Node> stack = new Stack<>();
            Stack<Node> stack1 = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()){
                Node cur = stack.pop();
                stack1.push(cur);
//                System.out.print(cur.value+"   ");

                if (cur.left!=null){
                    stack.push(cur.left);
                }
                if (cur.right!=null){
                    stack.push(cur.right);
                }
            }
            while (!stack1.isEmpty()){

                System.out.print(stack1.pop().value+"   ");
            }
        }
    }

    /**
     * 宽度遍历二叉树  先左，右遍历
     * @param head
     */
    public static void widthSearch(Node head){
       if (head!=null){
           Queue<Node> queue = new LinkedList<>();//队列
           queue.add(head);
           while (!queue.isEmpty()){
               Node cur = queue.poll();
               System.out.print(cur.value+"   ");
               if (cur.left!=null){
                   queue.add(cur.left);
               }
               if (cur.right!=null){
                   queue.add(cur.right);
               }
           }
       }
    }

    /**
     * 宽度遍历二叉树  先左，右遍历 ，找出最宽的节点个数
     * @param head
     */
    public static int widthSearchMax(Node head){
        if (head == null) {
            return 0;
        }
        int max = -1;
        int curLevel  = 1; // 默认为1层
        int curnum = 0;
        HashMap<Node, Integer> map = new HashMap();
        if (head!=null){
            Queue<Node> queue = new LinkedList<>();//队列
            queue.add(head);
            map.put(head,1);

            while (!queue.isEmpty()){
                Node cur = queue.poll();
                int curNodeLevel =  map.get(cur);
                if (curLevel == curNodeLevel){
//                    相等，说明没到下一层，继续统计个数（宽度）
                    curnum++;
                }else {
                    // 当前已是下一层了 （上一层已经遍历完成）
                max = Math.max(max,curnum); // 总结上一层的个数
                curLevel++;
                curnum = 1; // 重置当前节点个数  :
                    //     当前已出栈下一层的第一个节点，故宽度设为1
                }

                if (cur.left!=null){
                    queue.add(cur.left);
                    map.put(cur.left,curLevel+1);
                }
//                当前节点的右孩子不为空，队列加入右孩子，层数也变为当前节点的层数加1
                if (cur.right!=null){
                    queue.add(cur.right);
                    map.put(cur.right,curLevel+1);

                }
            }// 由于最后一层，没有新的一层去结算，所以这里单独结算最后一层
            max = Math.max(max,curnum);
        }
        return max;
    }

    /**
     * 先序 序列化
     * @param head
     */
    // 先序序列化
    public static Queue<Node> preSerial2(Node head) {
        Queue<Node> queue = new LinkedList<>();
        // 先序的序列化结果依次放入队列中去
        preSerializable(head, queue);
        return queue;
    }
    public  static  void preSerializable(Node head,Queue<Node> queue){
//        Queue<Node> queue = new LinkedList<>();

        if (head==null){
            queue.add(null);
        }else{
            queue.add(head);
            preSerializable(head.left,queue);
            preSerializable(head.right,queue);
        }
    }
    // 先序序列化
    public static Queue<String> preSerial(Node head) {
        Queue<String> ans = new LinkedList<>();
        // 先序的序列化结果依次放入队列中去
        pres(head, ans);
        return ans;
    }

    public static void pres(Node head, Queue<String> ans) {
        if (head == null) {
            ans.add(null);
        } else {
            ans.add(String.valueOf(head.value));
            pres(head.left, ans);
            pres(head.right, ans);
        }
    }

    /**
     * @ 先序反序列化
     * @param queue
     * @return
     */
    public static Node buildByPreQueue(Queue<Node> queue){
        if (queue.size()==0||queue.isEmpty()){
            return null;
        }else {

            Node poll = queue.poll();// 头节点
            // 如果头节点是空的话，返回空
            if (poll==null){
                return  null;
            }
            poll.left = buildByPreQueue(queue); // 设置该节点的左右节点
            poll.right = buildByPreQueue(queue);
            return poll;


        }
    }

    /**
     *  宽度优先遍历序列化
     * @param head
     * @return
     */
    public static Queue<Node> widthSearchSerializable(Node head){
        Queue<Node> nodeQueue = new LinkedList<>();
        if (head!=null){
            nodeQueue.add(head);
            Queue<Node> queue = new LinkedList<>();//辅助-->队列
            queue.add(head);
            while (!queue.isEmpty()){
                Node cur = queue.poll();
                if (cur.left!=null){
                    queue.add(cur.left);
                    nodeQueue.add(cur.left);
                }else {
                    nodeQueue.add(null);
                }
                if (cur.right!=null){
                    queue.add(cur.right);
                    nodeQueue.add(cur.right);

                }else {
                    nodeQueue.add(null);
                }
            }
        }else{
            nodeQueue.add(null);
        }
        return nodeQueue;
    }
    /*
    反序列化： 宽度遍历
     */
    public static Node buildByWidthSearchSerializable(Queue<Node> queue){

        if (queue.isEmpty()||queue.size()==0){
            return null;
        }
        Node poll =generateNode(queue.poll());
        if (poll != null) {
            Queue<Node> nodeQueue  = new LinkedList<>(); //辅助队列
            nodeQueue.add(poll);
            while (!nodeQueue.isEmpty()){
                Node node = nodeQueue.poll(); // 出队的是 辅助队列。。。
                node.left = queue.poll();
                node.right = queue.poll();
                if (node.left!=null){
                    nodeQueue.add(node.left);
                }
                if (node.right!=null){
                    nodeQueue.add(node.right);
                }
            }
                return poll;

        }else {
            return null;
        }

    }

    // 按层反序列化
    public static Node buildByLevelQueue(Queue<Node> levelList) {
        if (levelList == null || levelList.size() == 0) {
            return null;
        }
        Node head = generateNode(levelList.poll());
        Queue<Node> queue = new LinkedList<Node>();
        if (head != null) {
            queue.add(head);
        }
        Node node = null;
        while (!queue.isEmpty()) {
            node = queue.poll();
            // 不管左右孩子是否为空，都要加节点
            node.left = generateNode(levelList.poll());
            node.right = generateNode(levelList.poll());
            // 左孩子不为空，队列加左，为建下一层做准备
            if (node.left != null) {
                queue.add(node.left);
            }
            // 右孩子不为空，队列加右，为建下一层做准备
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return head;
    }
    public static Node generateNode(Node node) {
        if (node == null) {
            return null;
        }
        return node;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
//        head.left.left = new Node(4);
//        head.left.left.left = new Node(8);
//        head.left.left.right = new Node(9);

        head.left.right = new Node(5);

//        head.left.right.left = new Node(10);
        head.left.right.right = new Node(11);

        head.right.left = new Node(6);
        head.right.left.left = new Node(12);
        head.right.left.right = new Node(13);

        head.right.right = new Node(7);
        first(head);
        System.out.println(" 递归先序========");
        pre(head);
        System.out.println(" 非递归先序========");
        behind(head);
        //        behind2(head);不对
//        in(head);
        System.out.println(" 非递归后序========");
//        pos1(head);
//        System.out.println("宽度优先遍历 ========");
        widthSearch(head);
        System.out.println("宽度优先遍历 ========");
        System.out.println("宽度优先遍历寻求最宽节点数 ========");
        System.out.println(widthSearchMax(head));

//        pos2(head);

//            System.out.println(preSerializable(head));
        System.out.println("先序序列化========");
        System.out.println(preSerial(head));
        System.out.println("先序序列化 我写的========");
        Queue<Node> nodes = preSerial2(head);
        System.out.println(nodes);
        System.out.println("测试反序列化（先序）========");

        Node headNode = buildByPreQueue(nodes);
        first(headNode);

        System.out.println("宽度优先遍历序列化========");

        Queue<Node> nodeQueue = widthSearchSerializable(head);
        System.out.println(nodeQueue);

        System.out.println("测试反序列化（宽度）========");

        Node buildByWidthSearchSerializable = buildByWidthSearchSerializable(nodeQueue);
        widthSearch(buildByWidthSearchSerializable);
//        Node node = buildByLevelQueue(nodeQueue);
//        pre(node);

//
//            String a = "520";
//            a+=52;
//            System.out.println(a);

    }

}
